Search for: All records

In many automated motion planning systems, vehicles are tasked with tracking a reference path or trajectory that is safe by design. However, due to various uncertainties, real vehicles may deviate from such references, potentially leading to collisions. This paper presents rigorous reachable set bounding methods for rapidly enclosing the set of possible deviations under uncertainty, which is critical information for online safety verification. The proposed approach applies recent advances in the theory of differential inequalities that exploit redundant model equations to achieve sharp bounds using only simple interval calculations. These methods have been shown to produce very sharp bounds at low cost for nonlinear systems in other application domains, but they rely on problem-specific insights to identify appropriate redundant equations, which makes them difficult to generalize and automate. Here, we demonstrate the application of these methods to tracking problems for the first time using three representative case studies. We find that defining redundant equations in terms of Lyapunov-like functions is particularly effective. The results show that this technique can produce effective bounds with computational times that are orders of magnitude less than the planned time horizon, making this a promising approach for online safety verification. This performance, however, comes at the cost of low generalizability, specifically due to the need for problem-specific insights and advantageous problem structure, such as the existence of appropriate Lyapunov-like functions. 

This article presents a new method for accurately enclosing the reachable sets of nonlinear discrete-time systems with unknown but bounded disturbances. This method is motivated by the discrete-time differential inequalities method (DTDI) proposed by Yang and Scott, which exhibits state-of-the-art accuracy at low cost for many problems, but suffers from theoretical limitations that significantly restrict its applicability. The proposed method uses an efficient one-dimensional partitioning scheme to approximate DTDI while avoiding the key technical assumptions that limit it. Numerical result shows that this approach matches the accuracy of DTDI when DTDI is applicable, but, unlike DTDI, is valid for arbitrary systems.